package WinterHomework.day06;

//一个数组有两个数字出现了一次，其他都出现两次，找出这两个数字
public class Demo02 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 1, 2, 3, 4};
        int[] brr = findNnumberAppearOnce(arr);
        for (int i = 0; i < brr.length; i++) {
            System.out.println(brr[i]);
        }
    }

    public static int[] findNnumberAppearOnce(int[] arr) {
        if (arr == null || arr.length < 2) {
            return null;
        }
        //异或整个数组，得到两个只出现一次的数字的异或结果
        int ret = 0;
        for (int i = 0; i < arr.length; i++) {
            ret ^= arr[i];
        }
        int target = 1;
        //计算ret的哪一个二进制位为1
        while ((target & ret) == 0) {
            target <<= 1;
        }
        int num1 = 0;
        int num2 = 0;
        //对数组进行分组
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & target) == 1) {
                num1 ^= arr[i];
            } else {
                num2 ^= arr[i];
            }
        }
        return new int[]{num1, num2};
    }
}
